package demo.practice.leetcode;

import java.util.Stack;

public class P85 {


    public static void main(String[] args) {
        P85 p85= new P85();
        int caculate = p85.caculate(new int[]{4, 5, 2, 3});
        System.out.println(caculate);
    }

    public int maximalRectangle(char[][] matrix) {
        if(matrix==null||matrix.length==0|| matrix[0].length==0)
            return 0;

        int [] height= new int[matrix[0].length];
        int maximal=0;
        for( int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[i].length;j++){
                if(matrix[i][j]=='1')
                    height[j]++;
                else
                    height[j]=0;
            }
            maximal=Math.max(caculate(height),maximal);
        }
        return maximal;
    }

    public  int  caculate(int [] height){
        if(height==null || height.length==0)
            return 0;

        int maximal=0;
        Stack<Integer> stack= new Stack<>();

        for(int i=0;i<height.length;i++){

            while(!stack.isEmpty()&& height[i]<=height[stack.peek()]){
                int j= stack.pop();
                int k=stack.isEmpty()? -1:stack.peek();
                int area= (i-k-1)*height[j];
                maximal=Math.max(maximal,area);
            }
            stack.push(i);
        }

        while (!stack.isEmpty() ){
            int j=stack.pop();
            int k= stack.isEmpty()?-1:stack.peek();
            int area= (height.length-k-1)*height[j];
            maximal=Math.max(maximal,area);
        }

        return  maximal;
    }


}
